package ljl.alg.jianzhioffer.round2;

/**
 * 这个题非常的好
 *
 * */
public class _44_find_nth_digit {
    
    /**
     * 我感觉得先观察，找规律
     * 但是我没找到
     *
     * 规定这么三个变量
     * digit，当前在处理几位数
     * start，当前这 digit 位数的第一个数是几
     * count，这 digit 位数一共有多少位数字
     *
     * 目的是找到 n 这个数位，是哪个数的哪个位
     *
     * 递推公式是，digit 每次 += 1
     * start，是 digit * 10，错，是 start *= 10
     * count，是 digit * 9 * start
     *     这个我思考起来居然有些吃力
     *     比如 1 - 9，有多少 count？
     *     start(1) * digit(1) * 9
     *     10 - 90，多少？口算，180
     *     digit(2) * 10 * 9 对了
     *
     *     那公式就是 digit * 90
     *
     * 此外，n 能取到 int 最大值，所以 count 需要是 long
     *
     * */
    public int findNthDigit(int n) {
        // 错，start 和 count 需要是 long
        long start = 1, count = 9;
        int digit = 1;
        while (n > count) {
            n -= count;
            digit++;
            // start 忘了改了
            start *= 10;
            // 错，错的原因是：刚好我算的时候 start = 10，如果到 3 位必然就错了
            // 100 - 1000 有 900 * 3 = 2700 位
            // count = digit * 90;
            count = digit * start * 9;
        }
        // 找到是哪个数
        // 错，是 n - 1
        int offset = (n - 1) / digit;
        // 找到是哪个位
        int bit = String.valueOf(start + offset)
            // 错，没 - '0'
            .charAt(
                // 错，写成了 n
                (n - 1) % digit
            ) - '0';
        return bit;
    }
}
